רשימות המוגדרות בצורה רקורסיבית

מבנה נתונים ואלגוריתמים

אנו יכולים להגדיר רשימה כ:

א. ריקה

ב. או, מכילה חוליה וקישור לרשימה.

ניתן לסרוק רשימה תוך שימוש בפונקציה רקורסיבית: כגון: ספירת מספר הפריטים ברשימה:

 int ListCount( List l ) {
  if ( l == NULL ) return 0;
  else return 1 + ListCount( l->next );
  }

בכל אופן, מסתבר כי מהר יותר לכתוב פונקציה זו ללא קריאה רקורסיבית:

 int ListCount( List l ) {
  int cnt = 0;
  while ( l != NULL ) {
  cnt++;
  l = l->next;
  }
   return cnt;
  }

תקורת הקריאות לפונקציה הינה גדולה בכל מחשב, כך שהגרסה האינרטיבית מיושמת מהר יותר.

(פקטור נוסף במחשבים מודרניים הינו ההסתמכות הרבה על ה-cache: הקוד אינטרטיבי הנ"ל איננו משתמש בזיכרון רב מחסנית לקריאה ודבר זה מאפשר שימוש טוב יותר ב-cache.)

חזור ל: עצים חזור ל: תוכן עניינים